\documentclass[unicode]{beamer}
\mode<presentation>
\usepackage{beamerthemesplit}
\usetheme{Malmoe}
%\usepackage[cp1251]{inputenc}
\usepackage[english]{babel}
\usepackage[T2A]{fontenc}
\usepackage{amssymb,amsfonts,amsmath}
\usepackage {array}
\usepackage{graphicx}
\usepackage {gastex}
\usepackage{algorithm,algpseudocode}
\usepackage[]{color}%,dvips
\usepackage{pstricks,pst-node,pst-text}%,pst-3d
\definecolor{dred}{rgb}{0.6, 0, 0}

\expandafter\def\expandafter\insertshorttitle\expandafter{%
  \insertshorttitle\hfill%
  \insertframenumber\,/\,\inserttotalframenumber}

\def\append{{\bf append}}
\def\iappend{{\bf iappend}}
\def\len{{\bf len}}
\def\nextPal{{\bf nextPal}}
\def\maxPal{{\bf maxPal}}
\def\Pal{{Pal}}
\algtext*{EndWhile}% Remove "end while" text
\algtext*{EndIf}% Remove "end if" text
\algtext*{EndFunction}% Remove "end function" text
\algtext*{EndProcedure}% Remove "end procedure" text
\algtext*{EndFor}% Remove "end for" text

\let\OldComment\Comment
\renewcommand{\Comment}[1]{\OldComment{\textcolor{gray}{#1}}}


\author[Dmitry Kosolobov]{Dmitry Kosolobov}
\title[Lempel-Ziv Factorization and Runs]{Lempel-Ziv Factorization May Be Harder Than Computing All Runs}

\institute[]{Ural Federal University\\ Ekaterinburg, Russia}
\begin{document}
\date{ }
\maketitle

\section{Introduction}

\begin{frame}
\frametitle{Runs}
\begin{itemize}
\item<2-> $p$ is a \emph{period of $w$} if $w[i] = w[i{+}p]$ for $i = 1,2,\ldots,|w|{-}p$
\item<3-> $w$ is \emph{periodic} if it has a period $\le |w|/2$
\item<4-> $w[i..j] = w[i]w[i{+}1]\cdots w[j]$ is a \emph{substring} or a \emph{factor} of $w$
\item<5-> $w[i..j]$ is a \emph{run} if $w[i..j]$ is periodic and neither $w[i{-}1..j]$ nor $w[i..j{+}1]$ (if defined) is periodic
\end{itemize}
\visible<6->{
$w = {\color<7>{red}a}{\color<7>{red}b}{\color<7,9>{red}a}{\color<7,9>{red}b}{\color<7,8,9>{red}a}{\color<8,9>{red}a}{\color<9>{red}b}%
{\color<9>{red}a}$
$
\begin{array}{l}
\text{runs} \\
\hline
\color<7>{red}{w[1..5]} = ab\cdot ab\cdot a\\
\color<8>{red}{w[5..6]} = a\cdot a\\
\color<9>{red}{w[3..8]} = aba\cdot aba
\end{array}
$
}
\end{frame}

\begin{frame}
\frametitle{Lempel-Ziv factorization}
\visible<2->{
$w = u_1u_2\cdots u_k$ is the \emph{Lempel-Ziv factorization} if for $i = 1,\ldots,k$:
\begin{enumerate}
\item $u_i$ is a letter that does not appear in $u_1u_2\cdots u_{i-1}$ or
\item $u_i$ is the longest nonempty substring having at least two occurrences in $u_1u_2\cdots u_i$
\end{enumerate}
}
\visible<3->{
\begin{block}{Example}
$w = {\color<6,8>{red}a}{\color<6,8>{red}b}{\color<6,9>{red}a}{\color<9>{red}b}acab = {\color<4>{red}a}\cdot {\color<5>{red}b}\cdot {\color<6>{red}aba}\cdot {\color<7>{red}c}\cdot {\color<8,9>{red}ab}$
\end{block}
}
\end{frame}

\begin{frame}
\begin{block}{Theorem [Bannai et al. 2014]}
Any string of length $n$ has less than $n$ runs.
\end{block}
\pause
\begin{block}{Theorem [Kolpakov, Kucherov 1999]}
All runs in a string of length $n$ can be found in $O(n\log\sigma)$ time, where $\sigma$ is the number of distinct letters in the string.
\end{block}
\pause
\emph{Note: the Lempel-Ziv factorization is a bottleneck}
\pause
\begin{block}{Theorem [e.g., Crochemore, Ilie, Smyth 2008]}
The Lempel-Ziv factorization of a string of length $n$ over an integer alphabet bounded by $n^{O(1)}$ can be found in $O(n)$ time.
\end{block}
\pause
\begin{enumerate}
\item \textbf{Can we find the Lempel-Ziv factorization in $O(n)$ time on a~general alphabet?}\\
\pause
\item \textbf{Can we find all runs in $O(n)$ time on a general alphabet?}
\end{enumerate}
\end{frame}

\begin{frame}
\frametitle{Contribution}
\begin{block}{Theorem 1}
The construction of the Lempel-Ziv factorization of a string with at most $\sigma$ distinct letters requires $\Omega(n\log\sigma)$ comparisons of letters.
\end{block}
\pause
\begin{block}{Theorem 2}
To find all runs in a string over an ordered alphabet, it suffices to perform $O(n)$ comparisons of letters.
\end{block}
\pause
\emph{Note: we do not construct a RAM algorithm finding all runs}
\end{frame}

\section{Model of computation}

\begin{frame}
\frametitle{Model of computation}
\begin{picture}(108,40)(0,0)
\gasset{Nw=12,Nh=12,Nframe=n,AHnb=0}
\visible<2>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 5]{black_box}}}
\visible<3>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 5]{black_box2}}}
\visible<4>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 5]{black_box3}}}
\visible<5->{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 5]{black_box4}}}
\visible<6->{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 5]{black_box5}}}
\end{picture}
\begin{itemize}
\item<2-> The analyzed string is a black box
\item<4-> The alphabet is unordered \visible<5->{or ordered}
\item<6-> The algorithm is a \emph{decision tree}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Decision tree algorithms}
\pause
\begin{block}{Definition 1.1}
Runs of $u$ and $v$ are \emph{equivalent} if for each $i, j, p$, the string $u[i..j]$ is a run with the period $p$ iff $v[i..j]$ is a run with the period $p$.
\end{block}
\pause
\begin{block}{Definition 1.2}
A decision tree analyzing strings of length $n$ \emph{finds all runs} if any strings $u$ and $v$ reaching the same leaf have equivalent runs.
\end{block}
\pause
\begin{block}{Definition 2.1}
The Lempel-Ziv factorizations $u = u_1u_2\cdots u_k$ and $v = v_1v_2\cdots v_s$ are \emph{equivalent} if $k = s$ and $|u_i| = |v_i|$ for all $i = 1,\ldots,k$.
\end{block}
\pause
\begin{block}{Definition 2.2}
A decision tree analyzing strings of length $n$ \emph{finds the Lempel-Ziv factorization} if any strings $u$ and $v$ reaching the same leaf have equivalent Lempel-Ziv factorizations.
\end{block}
\end{frame}

\begin{frame}
\frametitle{The reformulation of our results}
\begin{block}{Theorem 1 (reformulated)}
On ordered alphabet, any decision tree finding the Lempel-Ziv factorization of strings of length $n$ with at most $\sigma$ distinct letters has height $\Omega(n\log\sigma)$.
\end{block}
\pause
\begin{block}{Theorem 2 (reformulated)}
On ordered alphabet, for any $n$, there is a decision tree of height $O(n)$ that finds all runs in strings of length $n$.
\end{block}
\pause
In contrast with
\begin{block}{Theorem [Main, Lorentz 1985]}
On unordered alphabet, any decision tree finding all runs in strings of length $n$ has height $\Omega(n\log n)$.
\end{block}
\end{frame}

\section{Lempel-Ziv factorization}

\begin{frame}
\frametitle{Informal reduction to dictionaries}
\begin{itemize}
\item<1-> $n$ is the length of the input string
\item<2-> $\{a_1 <\ldots<a_\sigma\}$ is an alphabet, $\sigma$ is even, $\sigma < n/2$, $\#=a_\sigma$
\item<3-> Consider $s = \#a_2\#a_4 \ldots \#a_{\sigma{-}2}$
\item<4-> $s$ is a ``dictionary'' of all ``even'' letters
\item<5-> Consider $t = \#a_{i_1}\#a_{i_2} \ldots \#a_{i_k}$
\item<6-> $t$ is a sequence of ``queries'' to the ``dictionary'' $s$
\item<7-> We are to find the Lempel-Ziv factorization of $st$
\end{itemize}
\visible<8->{
\begin{block}{Lempel-Ziv factors of $st$}
$$
\begin{array}{l}
\overbrace{\#a_2\#a_4 \cdots \#a_{\sigma{-}2}}^s \overbrace{{\color<10,11>{red}\#}{\color<10,11,12,13>{red}a_{i_1}}{\color<10,12>{red}\#}a_{i_2} \cdots \#a_{i_k}}^t \\
\visible<9->{\phantom{aaaaaaaaaaaaaaaaaa!}\uparrow} \\
\visible<10->{\text{\phantom{aaaaaaaaaa}If }a_{i_1}\text{\only<10-12>{ is even}\only<13->{ is odd}\phantom{d}}}
\end{array}
$$
\end{block}
}
\end{frame}

\begin{frame}
\frametitle{The key lemma}
\pause
$$
S = \left\{\begin{array}{c}
            \overbrace{\#a_2\#a_4 \cdots \#a_{\sigma{-}2}}^s \overbrace{\#a_{i_1}\#a_{i_2} \cdots \#a_{i_k}}^t\\
            \text{for }k\text{ such that }|st| = n\text{ and all even }i_1, \ldots, i_k
           \end{array}
    \right\}
$$
\pause
\emph{Note: $|S| = (\sigma / 2)^k$}%
\pause%
\emph{, $k = \Theta(n)$ since $\sigma < n/2$}
\pause
\begin{block}{Lemma}
Distinct strings $st, st' \in S$ reach distinct leafs in any decision tree finding the Lempel-Ziv factorization of strings of length $n$.
\end{block}
\pause
\begin{block}{Corollary}
Such decision tree has height $\ge \log_3 |S| = \Omega(k\log\sigma) = \Omega(n\log\sigma)$.
\end{block}
\end{frame}

\begin{frame}
\frametitle{Sketch of the proof of the lemma}
\begin{itemize}
\item<2-> Let, to the contrary, $st, st' \in S$ reach the same leaf and $t \ne t'$
\item<3->
$
\begin{array}{rl}
t = & \#a_6\#{\color{red}a_4}\# \cdots \#a_2 \\
t'= & \#a_6\#{\color{red}a_8}\# \cdots \#a_2
\end{array}
$
\item<4-> The decision tree could not ``distinguish'' $a_4$ and $a_8$
\item<5-> Thus, it won't ``distinguish'' $a_4$, $a_8$, and $a_5$ since $a_4 < a_5 < a_8$
\item<6-> $t'' = \#a_6\#{\color{red}a_5}\# \cdots \#a_2 $ reaches the same leaf (see the paper)
\item<7-> The Lempel-Ziv factorizations of $t$ and $t''$ are not equivalent:
$$
\begin{array}{rl}
t = & \#a_6{\color<7,8>{red}\#}{\color{red}a_4}{\color<7,9,10>{red}\#} \cdots \#a_2 \\
t''= & \#a_6\#{\color{red}a_5}\# \cdots \#a_2
\end{array}
$$
\item<10-> A contradiction
\end{itemize}
\end{frame}


\section{Idea of $O(n)$ solution}

\begin{frame}
\begin{block}{Example}
$$
\arraycolsep=0.5pt\def\arraystretch{0.8}
\begin{array}{r|ccccccccccccccccccc}
w =            &{\color<2,3,4>{red}\color<12>{green}b}&{\color<2,5,6,7>{red}\color<12>{green}a}&{\color<3,5,8,9,10>{red}\color<12>{green}b}&%
{\color<4,6,8>{red}\color<12>{green}a}&{\color<7,9>{red}\color<12>{green}b}&{\color<10>{red}\color<12,13>{green}\color<18->{blue}a}%
&{\color<13>{green}\color<18->{blue}a}&{\color<18->{blue}b}&{\color<18->{blue}c}&{\color<14>{green}\color<18->{blue}a}%
&{\color<14>{green}\color<18->{blue}a}&{\color<18->{blue}b}&{\color<18->{blue}c}&{\color<15>{green}\color<18->{blue}a}%
&{\color<15>{green}\color<18->{blue}a}&{\color<18->{blue}b}&\visible<11->{0&0&0} \\
\hline
\visible<2->{w[i] ? w[i{+}1]}&\visible<2->{{\color<2>{red}>}}&\visible<5->{{\color<5>{red}<}}&\visible<8->{{\color<8>{red}>}}%
&\visible<11->{<&>&{\color<13>{green}=}&<&<&>&{\color<14>{green}=}&<&<&>&{\color<15>{green}=}&<&>} \\
\visible<3->{w[i] ? w[i{+}2]}&\visible<3->{{\color<3>{red}\color<12>{green}=}}&\visible<6->{{\color<6>{red}\color<12>{green}=}}%
&\visible<9->{{\color<9>{red}\color<12>{green}=}}&\visible<11->{{\color<12>{green}=}&>&<&<&>&>&<&<&>&>&<&>&>} \\
\visible<4->{w[i] ? w[i{+}3]}&\visible<4->{{\color<4>{red}>}}&\visible<7->{{\color<7>{red}<}}&\visible<10->{{\color<10>{red}>}}%
&\visible<11->{=&=&<&=&>&>&<&=&>&>&>&>&>} \\
\visible<17->{w' = } &\visible<17->{x&y&x&z&r&{\color<19->{blue}s}&{\color<19->{blue}t}&{\color<19->{blue}v}&{\color<19->{blue}u}%
&{\color<19->{blue}s}&{\color<19->{blue}t}&{\color<19->{blue}v}&{\color<19->{blue}u}&q&v&u}
\end{array}
%bababaabcaabcaab
$$
\visible<16->{
$$
\begin{array}{llll}
q = \begin{pmatrix}=\\<\\>\end{pmatrix},
r = \begin{pmatrix}>\\>\\=\end{pmatrix},
s = \begin{pmatrix}=\\<\\<\end{pmatrix},
\ldots,
z = \begin{pmatrix}<\\=\\=\end{pmatrix}
\end{array}
$$
}
\begin{itemize}
\item<1-> Compare $w[i]$ and $w[i{+}j]$ for $i = 1,2,\ldots,|w|$ and $j = 1,2,3$
\item<12-> All runs with periods $\le 3$ are found
\item<16-> Deduce a new string $w'$ over a new constant alphabet
\item<18-> Each run of $w$ has a corresponding [``almost''] run of $w'$
\item<20-> There can be runs of $w'$ that do not correspond to runs of $w$
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{The algorithm}
\begin{enumerate}
\item<2-> Deduce $w'$ from $w$ in $O(n)$ comparisons
\item<3-> Find all runs of $w'$ in $O(n)$ comparisons
\item<4-> Find runs of $w$ corresponding to runs of $w'$
\end{enumerate}
\visible<5->{
The last step is performed using a recursion and some nonconstructive features of decision trees (see the full paper)
}
\end{frame}

\begin{frame}
\center{{\color{red}{Can we construct a RAM algorithm finding all runs in a~string of length $n$ in $O(n)$ time on a~general ordered alphabet?}}}
\pause
\center{\Huge{Thank you for your attention!}}
\end{frame}

\end{document}

